#include "subway.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define fi first
#define se second

using namespace std;

using vec = vector < int >;

int n, m, lim, ans, cnt;
vector < pair < int, int > > pot, stk[2];

void init(int N, int M, int L) {
	n = N, m = M, lim = L;
}

int solve(int l) {
	while(ans < m && check(ans + 1)) ++ans, pot.eb(ans, 1), merge(ans);
	if(!cnt) {
		vector < pair < int, int > > tpot;
		while(pot.size()) tpot.eb(pot.back()), undo(), pot.pop_back();
		pot.clear();
		for(auto v : tpot) merge(v.fi), pot.eb(v.fi, 0);
		cnt = pot.size();
	}
	if(pot.back().se == 1) {
		while(pot.back().se == 1) { stk[1].eb(pot.back()); pot.pop_back(); undo(); }
		int d = cnt & (-cnt);
		while(d--) { stk[0].eb(pot.back()); pot.pop_back(); undo(); }
		while(stk[1].size()) pot.eb(stk[1].back()), merge(stk[1].back().fi), stk[1].pop_back();
		while(stk[0].size()) pot.eb(stk[0].back()), merge(stk[0].back().fi), stk[0].pop_back();
	} undo(); pot.pop_back(); cnt--;
	return ans;
}
